package queue;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *
 * 969. 煎饼排序
 * 给你一个整数数组 arr ，请使用 煎饼翻转 完成对数组的排序。
 *
 * 一次煎饼翻转的执行过程如下：
 *
 * 选择一个整数 k ，1 <= k <= arr.length
 * 反转子数组 arr[0...k-1]（下标从 0 开始）
 * 例如，arr = [3,2,1,4] ，选择 k = 3 进行一次煎饼翻转，反转子数组 [3,2,1] ，得到 arr = [1,2,3,4] 。
 *
 * 以数组形式返回能使 arr 有序的煎饼翻转操作所对应的 k 值序列。任何将数组排序且翻转次数在 10 * arr.length 范围内的有效答案都将被判断为正确。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/pancake-sorting
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author : chenchao
 */
public class JianBingSort {
    public static void main(String[] args) {
//        int[] arr = new int[]{3,2,4,1};
        int[] arr = new int[]{9,8,4,1,3,2,6,5,7};
//        List<Integer> res = new Solution2().pancakeSort(arr);
        List<Integer> res = new Solution().pancakeSort(arr);

        System.out.println("res:"+res);
        for(Integer i : res){
            System.out.print(i);
        }
    }

    static class Solution {
        public List<Integer> pancakeSort(int[] arr) {
            List<Integer> ret = new ArrayList<Integer>();

            int[] indexArr = new int[arr.length+1];

            for(int i=0;  i<arr.length; i++){
                indexArr[arr[i]] = i;
            }

            for(int i = indexArr.length-1; i>=1; i--){
                int targetIndex = indexArr[i];

                //如果该最值已经在目标位置了
                if(targetIndex == i){
                    continue;
                }
                //如果该最值已经在第一个位置了，跳过将它翻转到第一个位置
                if(targetIndex != 0){
                    ret.add(targetIndex+1);
                    reverse(arr,targetIndex, indexArr);
                }
                //如果目标位置是第一个位置，不用再做二次翻转了
                if(i != 1){
                    ret.add(i);
                    reverse(arr,i-1, indexArr);
                }
            }

            return ret;
        }

        public void reverse(int[] arr,int n, int[] indexArr){
            int mid = n/2;

            for(int i=0; i<=mid; i++){
                int tmp = arr[n-i];
                arr[n-i] = arr[i];
                arr[i] = tmp;

                indexArr[arr[n-i]] = n-i;
                indexArr[arr[i]] = i;
            }
        }
    }

    static class Solution2 {
        public List<Integer> pancakeSort(int[] arr) {
            ArrayList<Integer> result = new ArrayList<>();
            for (int i = arr.length; i > 0; i--) {
                int index = 0;
                while (arr[index] != i) {
                    index++;
                } if (index == i - 1) {
                    continue;
                } else if (index == 0) {
                    reverse(arr, i);

                    result.add(i);
                } else {
                    reverse(arr, index + 1);
                    result.add(index + 1);
                    reverse(arr, i);
                    result.add(i);
                }
            } return result;
        }
        public void reverse(int[] arr, int index) {
            int start = 0, end = index - 1;
            while (start < end) {
                int temp = arr[end];
                arr[end] = arr[start];
                arr[start] = temp;
                start++;
                end--;
            }
        }
    }
}
